package binarysearch;

import org.junit.Test;

import java.util.Arrays;

public class MedianOfTwoSortedArrays4 {

    @Test
    public void test() {
        print1(new int[]{1, 3}, new int[]{2});
        print1(new int[]{1, 2}, new int[]{3, 4});
        print1(new int[]{1, 2}, new int[]{3, 4, 5});
        print1(new int[]{1, 2}, new int[]{3, 4, 5, 6});
        print1(new int[]{0, 0}, new int[]{0, 0});
        print1(new int[]{0, 0, 0, 0, 0}, new int[]{-1, 0, 0, 0, 0, 0, 1});
    }

    public void print1(int[] n1, int[] n2) {
        System.out.format("n1: %s, n2: %s, result: %4f\n", Arrays.toString(n1), Arrays.toString(n2), findMedianSortedArrays1(n1, n2));
    }

    public double findMedianSortedArrays1(int[] n1, int[] n2) {
        boolean hasTwo = ((n1.length + n2.length) % 2 == 0);
        int firstSeq = (n1.length + n2.length + 1) / 2;
        int i = 0;
        int j = 0;
        int midSum = 0;
        while (i < n1.length && j < n2.length) {
            int smaller;
            if (n1[i] <= n2[j]) {
                smaller = n1[i];
                i++;
            } else {
                smaller = n2[j];
                j++;
            }
            if (hasTwo) {
                if (i+j == firstSeq) {
                    midSum = smaller;
                } else if (i+j == firstSeq+1) {
                    midSum += smaller;
                    return midSum/2.0d;
                }
            } else {
                if (i+j == firstSeq) {
                    midSum = smaller;
                    return midSum;
                }
            }
        }

        int seq = i + j + 1;
        int[] n;
        int k;
        if (i == n1.length) {
            n = n2;
            k = j;
        } else {
            n = n1;
            k = i;
        }

        while (k < n.length) {
            if (hasTwo) {
                if (seq == firstSeq) {
                    midSum = n[k];
                } else if (seq == firstSeq+1) {
                    midSum += n[k];
                    return midSum/2.0d;
                }
            } else {
                if (seq == firstSeq) {
                    midSum = n[k];
                    return midSum;
                }
            }
            seq++;
            k++;
        }

        if (hasTwo) {
            return midSum/2.0d;
        } else {
            return midSum;
        }
    }
}
